import sun.reflect.generics.tree.Tree;

public class AVLTree {
    static class TreeNode {
        public int val;
        public int bf;//平衡因子
        public TreeNode left;
        public TreeNode right;
        public TreeNode parent;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode root;
    public boolean insert(int val) {
        TreeNode node = new TreeNode(val);
        if(root == null) {
            root = node;
            return true;
        }
        TreeNode parent = null;
        TreeNode cur = root;
        while(cur != null) {
            parent = cur;
            if(cur.val < val) {
                cur = cur.right;
            } else if(cur.val > val) {
                cur = cur.left;
            } else {
                return false;
            }
        }
        if(parent.val < val) {
            parent.right = node;
        } else {
            parent.left = node;
        }
        node.parent = parent;
        cur = node;
        //调整平衡因子bf
        while(parent != null) {
            //cur插在右边，parent.bf++，cur插在左边，parent.bf--
            if(parent.right == cur) {
                parent.bf++;
            } else {
                parent.bf--;
            }
            if(parent.bf == 0) {
                //若parent.bf变为0，则已经平衡
                break;
            } else if(parent.bf == 1 || parent.bf == -1) {
                //若parent.bf变为1或-1，parent和cur向上迭代调整
                cur = parent;
                parent = parent.parent;
            } else {
                if(parent.bf == 2) {
                    //若parent.bf变为2，说明右树过高，需要左旋
                    if(cur.bf == 1) {
                        rotateLeft(parent);//bf同号，触发左旋
                    } else {
                        rotateRightLeft(parent);//bf异号，触发右左双旋
                    }
                } else {
                    //若parent.bf变为-2，说明左树过高，需要右旋
                    if(cur.bf == -1) {
                        rotateRight(parent);//bf同号，触发右旋
                    } else {
                        rotateLeftRight(parent);//bf异号，触发左右双旋
                    }
                }
                break;//经历旋转后，旋转部分组成的子树已平衡，整棵树一定平衡
            }
        }
        return true;
    }
    private void rotateRight(TreeNode parent) {
        TreeNode cur = parent.left;
        TreeNode curRight = cur.right;
        TreeNode parentParent = parent.parent;

        parent.left = curRight;
        if(curRight != null) {
            curRight.parent = parent;
        }
        cur.right = parent;
        parent.parent = cur;

        if(parent == root) {
            root = cur;
            cur.parent = null;
        } else {
            if(parentParent.left == parent) {
                parentParent.left = cur;
            } else {
                parentParent.right = cur;
            }
            cur.parent = parentParent;
        }

        cur.bf = 0;
        parent.bf = 0;
    }
    private void rotateLeft(TreeNode parent) {
        TreeNode cur = parent.right;
        TreeNode curLeft = cur.left;
        TreeNode parentParent = parent.parent;

        parent.right = curLeft;
        if(curLeft != null) {
            curLeft.parent = parent;
        }
        cur.left = parent;
        parent.parent = cur;

        if(parent == root) {
            root = cur;
            cur.parent = null;
        } else {
            if(parentParent.left == parent) {
                parentParent.left = cur;
            } else {
                parentParent.right = cur;
            }
            cur.parent = parentParent;
        }

        cur.bf = 0;
        parent.bf = 0;
    }
    private void rotateLeftRight(TreeNode parent) {
        TreeNode cur = parent.left;
        TreeNode curRight = cur.right;
        int bf = curRight.bf;
        rotateLeft(cur);
        rotateRight(parent);
        if(bf == -1) {
            parent.bf = 1;
            cur.bf = 0;
            curRight.bf = 0;
        } else if(bf == 1) {
            parent.bf = 0;
            cur.bf = -1;
            curRight.bf = 0;
        }
    }
    private void rotateRightLeft(TreeNode parent) {
        TreeNode cur = parent.right;
        TreeNode curLeft = cur.left;
        int bf = curLeft.bf;
        rotateRight(cur);
        rotateLeft(parent);
        if(bf == 1) {
            parent.bf = -1;
            cur.bf = 0;
            curLeft.bf = 0;
        } else if(bf == -1) {
            parent.bf = 0;
            cur.bf = 1;
            curLeft.bf = 0;
        }
    }


    public void inOrder(TreeNode root) {
        if(root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    public int height(TreeNode root) {
        if(root == null) return 0;
        int left = height(root.left);
        int right = height(root.right);
        return Math.max(left, right) + 1;
    }
    private boolean isBalance(TreeNode root) {
        if(root == null) return true;
        int leftH = height(root.left);
        int rightH = height(root.right);
        //检查平衡因子
        if(rightH - leftH != root.bf) {
            System.out.println(root.val+" 平衡因子异常！");
            return false;
        }
        return Math.abs(leftH-rightH) <= 1 &&
                isBalance(root.left) && isBalance(root.right);
    }

    public static void main(String[] args) {
        AVLTree avlTree = new AVLTree();
        //int[] arr = {16, 3, 7, 11, 9, 26, 18, 14, 15};
        int[] arr = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};
        for(int i : arr) {
            avlTree.insert(i);
        }
        avlTree.inOrder(avlTree.root);
        System.out.println(avlTree.isBalance(avlTree.root));
    }
}
